package greed;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : PartitionLabels
 * @Description : 763. 划分字母区间
 * https://leetcode.cn/problems/partition-labels/
 * @Author : chentianyu
 * @Date 2023/2/24 00:07
 */


public class PartitionLabels {
    public List<Integer> partitionLabels(String s) {
        int[] map = new int[26];
        for (int i=0; i<s.length(); i++) {
            map[s.charAt(i)-'a'] = i;
        }
        List<Integer> ans = new ArrayList<>();
        int l = 0, r = map[s.charAt(0)-'a'];
        for (int i=0; i<s.length(); i++) {
            r = Math.max(r, map[s.charAt(i)-'a']);
            if (i == r) {
                ans.add(r - l + 1);
                l = i + 1;
            }
        }
        return ans;
    }
}
